#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;
#define MAX_N 50000
int f[MAX_N];
int N1,N2;

int foo1(string s1, string s2)
{
    N1 = s1.size();
    N2 = s2.size();
    if(s1[0] == s2[0])
        f[1] = 0;
    else
        f[1] = 1;
    for (int k=2;k<=N2;k++)
    {
        f[k] = f[k-1];
        if(s1[k-1] != s2[k-1])
            f[k]++;
    }
    for (int k=N2;k<=N1;k++)
    {
        for (int i=1;i<=N2;i++)
        {
            int ii = k - N2 + i;
            int jj = i;

            if (s1[ii-1] == s2[jj-1])
                f[i] = min(f[i], f[i-1]);
            else if(i > 1)
                f[i] = min(f[i], f[i-1]+1);
        }
    }
    return f[N2];
}
int foo(string s1,string s2)
{

    N1 = s1.size();
    N2 = s2.size();
    int minx = N1;
    for (int i = 0; i<=N1-N2;i++)
    {
        int nn=0;
        for(int j=0;j<N2;j++)
            if(s1[i+j] != s2[j])
                nn++;
        minx =min(minx,nn);
    }
    return minx;
}
int main()
{
    int T;
    string s1,s2;
    cin>>T;
    for (int t = 1; t <= T; t++)
    {
        cin>>s1>>s2;
        int n = foo(s1.c_str(),s2);
        cout<<"Case #"<<t<<": "<<n;
        if(t != T)
            cout<<endl;
    }
    /*
    */
    //cout<<foo("0123456789","321")<<endl;
    //cout<<foo("010203040506070809","404")<<endl;
    //cout<<foo("20121221","211")<<endl;
    return 0;
}

